class node(object):
    word = None
    pre = None

    def __init__(self, _word, _pre):
        self.word = _word
        self.pre = _pre


def diff_one(a, b):
    count = 0
    for i in xrange(len(a)):
        if a[i] != b[i]:
            if count == 1:
                return False
            count += 1
    return True


def generage_graph(wordList):
    graph = {}
    for i in wordList:
        for j in wordList:
            if diff_one(i, j):
                if i in graph:
                    graph[i].append(j)
                else:
                    graph[i] = [j]
    return graph


def find_ladders(beginWord, endWord, wordList):
    wordList.append(beginWord)
    graph = generage_graph(wordList)
    
    start = node('hit', None)
    if_find = False
    now = [start]
    while not if_find:
        new = []
        for i in now:
            for j in graph[i.word]:
                if j == endWord:
                    if_find = True
                new.append(node(j, i))
        now = new
    arrivals = [i for i in now if i.word == endWord]
    paths = []
    for i in arrivals:
        path = find_path(i, [])
        path = path[::-1]
        paths.append(path)
    for i in paths:
        print i
    return paths


def find_path(end, path):
    path.append(end.word)
    if end.pre is None:
        return path
    else:
        return find_path(end.pre, path)


begin_word = 'hit'
end_word = 'cog'
word_list = ['hot', 'dot', 'dog', 'lot', 'log', 'cog']
find_ladders(begin_word, end_word, word_list)
